package com.explorati.LeetCode040.combinationSum2;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.*;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 23:27 2020/10/4 0004
 * @ Description ：
 */
public class Solution {
    /**
     * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     *
     * candidates 中的每个数字在每个组合中只能使用一次。
     *
     * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
     * 所求解集为:
     * [
     *   [1, 7],
     *   [1, 2, 5],
     *   [2, 6],
     *   [1, 1, 6]
     * ]
     *
     * @param candidates
     * @param target
     * @return
     */
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // candidates 中每个数字在组合中只能使用一次

        if(candidates.length == 0) {
            return res;
        }

        Arrays.sort(candidates);
        used = new boolean[candidates.length];

        Deque<Integer> preList = new ArrayDeque<>();
        findCombinations(candidates, 0, preList, target);
        return res;
    }

    private void findCombinations(int[] candidates, int index, Deque<Integer> preList, int target) {
        if(target == 0) {
            res.add(new ArrayList<>(preList));
            return ;
        }

        for(int i = index; i < candidates.length; i ++) {
            // 剪枝优化
            if(target - candidates[i] < 0) {
                return;
            }

            //如果当前位置的元素使用过 或者 当前位置元素和前一个位置元素相同，并且前一个位置的元素没有使用，跳过
            if(used[i] || (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1])) {
                continue;
            }

            preList.add(candidates[i]);
            used[i] = true;
            findCombinations(candidates, i + 1, preList, target - candidates[i]);
            used[i] = false;
            preList.removeLast();
        }
    }
}
